package cn.xaut.动态规划;

import static java.lang.Math.*;

public class Knapsack {

    // 动态规划（空间究极优化）O(C)
    public int knapsack01_4(int[] w, int[] v, int C) {
        
        int n = w.length;
        if (n == 0 || C == 0)
            return 0;

        int[] dp = new int[C + 1];

        for (int i = 0; i <= C; i++) 
            dp[i] = i >= w[0] ? v[0] : 0;

        for (int i = 1; i < n; i++) {
            for (int j = C; j >= 0; j--) {
                if (j < w[i])
                    break;
                // 当前物品装得下
                dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
            }
        }
        
        return dp[C];
    }
    
    // 动态规划（空间优化）
    public int knapsack01_3(int[] w, int[] v, int C) {

        int n = w.length;
        if (n == 0 || C == 0)
            return 0;

        // 初始化
        // dp[i] 表示用 [0...index] 的物品，填充容积为 C 的背包的最大价值
        int[][] dp = new int[2][C + 1];

        // 基础状态
        for (int i = 0; i <= C; i++)
            dp[0][i] = i >= w[0] ? v[0] : 0;

        // 状态转移
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= C; j++) {
                if (j >= w[i])  // 当前物品装得下
                    dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], v[i] + dp[(i - 1) % 2][j - w[i]]);  // 装 or 不装 取最大
                else    // 装不下
                    dp[i % 2][j] = dp[(i - 1) % 2][j];
            }
        }

/*        for (int i = 0; i < n; i++) {     // 输出表格
            for (int j = 0; j <= C; j++) 
                System.out.print(dp[i][j] + "\t");
            System.out.println();
        }*/

        return dp[(n - 1) % 2][C];
    }

    // 动态规划
    public int knapsack01(int[] w, int[] v, int C) {
        
        int n = w.length;
        if (n == 0 || C == 0)
            return 0;
        
        // 初始化
        // dp[i] 表示用 [0...index] 的物品，填充容积为 C 的背包的最大价值
        int[][] dp = new int[n][C + 1];
        
        // 基础状态
        for (int i = 0; i <= C; i++) 
            dp[0][i] = i >= w[0] ? v[0] : 0;
        
        // 状态转移
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= C; j++) {
                if (j >= w[i])  // 当前物品装得下
                    dp[i][j] = Math.max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);  // 装 or 不装 取最大
                else    // 装不下
                    dp[i][j] = dp[i - 1][j];
            }
        }

/*        for (int i = 0; i < n; i++) {     // 输出表格
            for (int j = 0; j <= C; j++) 
                System.out.print(dp[i][j] + "\t");
            System.out.println();
        }*/
        
        return dp[n - 1][C];
    }

    
    int[][] memo;
    // 记忆化搜索
    public int knapsack01_2(int[] w, int[] v, int C) {
        
        int n = w.length;
        
        memo = new int[n][C + 1];

        return bestValue(w, v, n - 1, C);
    }

    // 用 [0...index] 的物品，填充容积为 C 的背包的最大价值
    private int bestValue(int[] w, int[] v, int index, int C) {
        
        // 递归终止条件
        if (index < 0 || C <= 0)
            return 0;
        if (memo[index][C] != 0)
            return memo[index][C];

        // 递归过程
        if (C >= w[index])  // 装得下                          不装 ↓                装 ↓
            memo[index][C] = Math.max(bestValue(w, v, index - 1, C), v[index] + bestValue(w, v, index - 1, C - w[index]));
        else    // 装不下
            memo[index][C] = bestValue(w, v, index - 1, C);
        
        return memo[index][C];
    }

    public static void main(String[] args) {

        System.out.println(new Knapsack().knapsack01(new int[]{1, 2, 3}, new int[]{6, 10, 12}, 5)); // 22
        System.out.println(new Knapsack().knapsack01_2(new int[]{1, 2, 3}, new int[]{6, 10, 12}, 5)); // 22
        System.out.println(new Knapsack().knapsack01_3(new int[]{1, 2, 3}, new int[]{6, 10, 12}, 5)); // 22
        System.out.println(new Knapsack().knapsack01_4(new int[]{1, 2, 3}, new int[]{6, 10, 12}, 5)); // 22
    }
}
